package com.gxc.recursion;

public class Construct {

    public Node construct(int[][] grid) {
        return recursion(0 , 0 , grid.length-1, grid[0].length-1, grid);
    }

    private Node recursion(int x, int y ,int x1, int y1, int[][] grid) {
        if (x == x1 && y == y1) return new Node(grid[x][y] == 1, true);

        int mid = (x1 - x + 1) / 2;
        Node topLeft = recursion(x, y , x + mid-1, y + mid-1, grid);
        Node topRight = recursion(x, y+mid , x + mid-1, y1, grid);
        Node bottomLeft = recursion(x+mid, y , x1, y + mid-1, grid);
        Node bottomRight = recursion(x+mid, y+mid , x1, y1, grid);

        boolean isLeaf = topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf;
        boolean val = topLeft.val && topRight.val && bottomLeft.val && bottomRight.val;
        boolean union = true;
        boolean base = topLeft.val == topRight.val;
        if (base) {
            base = topLeft.val == bottomLeft.val;
        }
        if (base) {
            base = topLeft.val == bottomRight.val;
        }
        if (!base) union = false;

        if (isLeaf && union) return new Node(topLeft.val, true);
        else return new Node(val, val, topLeft, topRight, bottomLeft, bottomRight);
    }

}

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;


    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}
